//实现双端队列

import sun.net.idn.Punycode;

import java.util.LinkedList;

//用双向链表实现双端队列
class MyCircularDeque1{
    private LinkedList<Integer> deque = new LinkedList<>();
    private int size;
    private int limit;
    public MyCircularDeque1(int k) {
        this.size = 0;
        this.limit = k;
    }

    //判断空
    public boolean isEmpty() {
        return size == 0;
    }
    //判断满
    public boolean isFull() {
        return size == limit;
    }
    //头入
    public void insertFront(int data) {
        if(isFull()){
            throw new DequeOutOfException("队列已满");
        }
        deque.offerFirst(data);
        size++;
    }
    //尾入
    public void insertBack(int data) {
        if(isFull()){
            throw new DequeOutOfException("队列已满");
        }
        deque.offerLast(data);
        size++;
    }
    //头出
    public int delFront() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列为空");
        }
        int temp = deque.pollFirst();
        size--;
        return temp;
    }
    //尾出
    public int delBack() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列为空");
        }
        int temp = deque.pollLast();
        size--;
        return temp;
    }
    //获取头元素
    public int getFront() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列为空");
        }
        return deque.peekFirst();
    }
    //获取尾元素
    public int getBack() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列为空");
        }
        return deque.peekLast();
    }


}

//用数组实现双端队列
class MyCircularDeque2 {
    private int[] deque;
    private int head;
    private int tail;
    private int size;
    private int limit;
    public MyCircularDeque2(int k) {
        deque = new int[k];
        head = tail = size = 0;
        limit = k;
    }
    //判断空
    public boolean isEmpty() {
        return size == 0;
    }
    //判断满
    public boolean isFull() {
        return size == limit;
    }
    /**插入和删除逻辑
     * 头入： head=0时 head = limit -1;  head != 0时  head--
     * 头删： head=limit-1时 head = 0;   head !=limit - 1时，head++
     *
     * 尾入： tail = limit - 1时 tail = 0;  tail != limit -1 时 tail++
     * 尾删： tail = 0 时 tail = limit - 1; tail !=0 时 tail--
     */

    //头插
    public void insertFront(int val) {
        if(isFull()) {
            throw new DequeOutOfException("队列已满");
        }
        if(isEmpty()) {
            head = tail = 0;
            deque[head] = val;
        }else {
            head = head == 0 ? limit - 1 : head - 1;
            deque[head] =val;
        }
        size++;
    }
    //尾插
    public void insertBack(int val){
        if(isFull()) {
            throw new DequeOutOfException("队列已满，插入失败");
        }
        if(isEmpty()) {
            head = tail = 0;
            deque[tail] = val;
        }else {
            tail = tail == limit-1 ? 0 : tail + 1;
            deque[tail] =val;
        }
        size++;
    }

    //头删
    public int delFront() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列已空，删除失败");
        }
        size--;
        if(head == limit-1) {
            head = 0;
            return deque[limit-1];
        }else {
            head++;
            return deque[head-1];
        }
    }
    //尾删
    public int delBack() {
        if(isEmpty()) {
            throw new DequeEmptyException("队列已空，删除失败");
        }
        size--;
        if(tail == 0) {
            tail = limit-1;
            return deque[0];
        }else {
            tail--;
            return deque[tail+1];
        }
    }
    //返回头位置元素
    public int getHead() {
        return deque[head];
    }
    //返回尾位置元素
    public int getTail() {
        return deque[tail];
    }
    //清空数据
    public void clear() {
        head = tail = 0;
        size = 0;
    }

}

public class DeQueueTest {
    public static void main(String[] args) {
        //用第一种方法创建
        MyCircularDeque1 deque1 = new MyCircularDeque1(5);
        deque1.insertFront(5);
        deque1.insertFront(6);
        deque1.insertBack(1);
        deque1.insertBack(2);
        deque1.insertBack(3); //65123
        System.out.println(deque1.getFront()); //6
        System.out.println(deque1.getBack());  //3
        //deque1.insertFront(7);
        deque1.delFront();
        deque1.delFront();//123
        System.out.println(deque1.getFront()); //1
        System.out.println(deque1.getBack());  //3

        //用第二种方法创建
        MyCircularDeque2 deque2 = new MyCircularDeque2(5);
        deque2.insertBack(3);
        deque2.insertBack(5);
        deque2.insertBack(6);
        deque2.insertFront(8);
        deque2.insertFront(1);  //18356
        System.out.println(deque2.getHead()); //1
        System.out.println(deque2.getTail()); //6
        deque2.delBack();
        deque2.delBack();//183
        System.out.println(deque2.getHead()); //1
        System.out.println(deque2.getTail()); //3

    }
}
